# 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
# 输入: root = [3,1,4,null,2], k = 1
#    3
#   / \
#  1   4
#   \
#    2
# 输出: 4


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        lst = []

        def f(root):
            if not root:
                return
            f(root.left)
            lst.append(root.val)
            f(root.right)
        f(root)
        return lst[-k]


class Solution1:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k = k

        def f(root):
            if not root:
                return
            f(root.right)
            if self.k == 0:
                return
            if self.k - 1 == 0:
                self.res = root.val
            self.k -= 1
            f(root.left)
        f(root)
        return self.res


